/*
给出一个字符串 s（仅含有小写英文字母和括号）。

请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。

注意，您的结果中 不应 包含任何括号。

示例 1：

输入：s = "(abcd)"
输出："dcba"
示例 2：

输入：s = "(u(love)i)"
输出："iloveu"
示例 3：

输入：s = "(ed(et(oc))el)"
输出："leetcode"
示例 4：

输入：s = "a(bcdefghijkl(mno)p)q"
输出："apmnolkjihgfedcbq"

提示：

0 <= s.length <= 2000
s 中只有小写英文字母和括号
我们确保所有括号都是成对出现的
*/

#include "stdc++.h"

/* 栈
时间复杂度：O(n^2)，主要是每一层的反转也需要O(n)
*/
class Solution {
public:
    string reverseParentheses(string s) {
        string res = "";
        stack<string> stk{};
        for (auto& c : s) {
            if (c == '(') {
                stk.push(res);
                res = "";
            } else if (c == ')') {
                reverse(res.begin(), res.end());
                res = stk.top() + res;
                stk.pop();
            } else {
                res += c; // 小写字母
            }
        }
        return res;
    }
};

/* 预处理括号的位置
时间复杂度：O(n)
*/
class Solution {
public:
    string reverseParentheses(string s) {
        int n = s.length();
        vector<int> pair(n);
        stack<int> stk{};
        for (int i{0}; i < n; ++i) {
            if (s[i] == '(') {
                stk.push(i); // 记录左括号下标
            } else if (s[i] == ')') {
                int j = stk.top();
                stk.pop();
                pair[i] = j;
                pair[j] = i;
            }
        }
        string res{};
        int index{0};
        int step{1};
        while (index < n) {
            if (s[index] == '(' || s[index] == ')') {
                index = pair[index];
                step = -step; // 遇到左右括号都需要改变方向
            } else {
                res += s[index];
            }
            index += step;
        }
        return res;
    }
};